package com.markus.code.动态规划;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/17 19:09
 * todo: 分割回文串
 */
public class LeetCode_131 {
    /**
     * 这个题我的思路是先通过范围尝试模型得出一个dp表用来表示字符串的某一范围下是否是回文子串
     * 再通过回溯的方式去解决
     */
    public List<List<String>> partition(String s) {
        List<List<String>> ansList = new ArrayList<>();
        if (s == null || s.length() == 0){
            return ansList;
        }
        Deque<String> res = new ArrayDeque<>();
        char[] str = s.toCharArray();
        boolean[][] dp = getDP(str);
        process(s,dp,0,res,ansList);
        return ansList;
    }
    private void process(String str,boolean[][] dp,int index,Deque<String> res,List<List<String>> ans){
        if (index == str.length()){
            ans.add(new ArrayList<>(res));
            return ;
        }
        for (int i=index;i<str.length();i++){
            if (!dp[index][i]){
                continue;
            }
            res.addLast(str.substring(index,i+1));
            process(str,dp,i+1,res,ans);
            res.removeLast();
        }
    }

    private boolean[][] getDP(char[] str){

        boolean[][] dp = new boolean[str.length][str.length];
        //先填基本数据
        for (int i=0;i<str.length;i++){
            dp[i][i] = true;
            if (i != str.length-1){
                dp[i][i+1] = str[i]==str[i+1]?true:false;
            }
        }
        //再填普遍数据
        for (int i=dp.length-3;i>=0;i--){
            for (int j=i+2;j<dp[i].length;j++){
                dp[i][j] = str[i]==str[j] && dp[i+1][j-1];
            }
        }
        return dp;
    }

    public static void main(String[] args) {
        String s = "aab";
        LeetCode_131 demo = new LeetCode_131();
        List<List<String>> partition = demo.partition(s);
        System.out.println("开始");
        for (List<String> list : partition) {
            for (String s1 : list) {
                System.out.print(s1+" ");
            }
            System.out.println();
        }
        System.out.println("结束");
    }
}
